package com.leetcode.algorithm.y22.m08.w5;

import java.util.stream.IntStream;

/**
 * 1005. K 次取反后最大化的数组和
 * 
 * https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
 * 
 * @author jie.deng
 *
 */
class Question1005Solution01 {

	// 贪心算法
	public int largestSumAfterKNegations(int[] nums, int k) {
		// 前提条件：
		// 局部最优：让绝对值大的负数变为正数
		// 全局最优：整个数组和达到最大
		
		// 绝对值小的排在前面
		nums = IntStream.of(nums)
				.boxed()
				.sorted((t1, t2) -> Math.abs(t1) - Math.abs(t2))
				.mapToInt(Integer::intValue)
				.toArray();

		int len = nums.length;
		int cnt = 0;
		int idx = len - 1;
		int sum = 0;
		while (cnt < k && idx >= 0) {
			if (nums[idx] < 0) {
				cnt++;
				sum -= nums[idx];
			} else {
				sum += nums[idx];
			}
			idx--;
		}
		if (idx >= 0) {
			while (idx >= 0) {
				sum += nums[idx];
				idx--;
			}
		} else {
			if (((k - cnt) & 1) == 1) {
				sum -= 2 * Math.abs(nums[0]);
			}
		}
		return sum;
	}

}